/**
 * @Author Fizz Pu
 * @Date 2020/9/8 下午8:15
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

/**
 * 有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。
 * 由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。
 * 编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
 *
 * 示例：
 *
 * 输入：
 * [
 *   [0,2,1,0],
 *   [0,1,0,1],
 *   [1,1,0,1],
 *   [0,1,0,1]
 * ]
 * 输出： [1,2,4]
 * 提示：
 *
 * 0 < len(land) <= 1000
 * 0 < len(land[i]) <= 1000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/pond-sizes-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 第一反应是深度优先搜索
 * 1. 从0开始深搜，搜索方向是上下左右对角
 * 2. 搜索第二个0处，确保这个0没有被搜索过，所以需要一个东西来保存已经被搜过的0
 * 3. 每一次搜索需要保存搜到的零的个数，排序后返回。
 */


// 第一次没有搞出来，看了大神的代码，太nb了
public class Lee1619 {
    public static void main(String[] args) {
        int[][] land = new int[][]{
            {0,2,1,0},{0,1,0,1},{1,1,0,1},{0,1,0,1}
        };
        System.out.println(Arrays.toString(new Lee1619().pondSizes(land)));
    }

    public int[] pondSizes(int[][] land){
            List<Integer> res = new ArrayList<>();
            for(int i = 0; i < land.length; ++i){
                for(int j = 0; j < land[0].length; ++j){
                    // 从0开始搜索
                    if(land[i][j] == 0){
                        res.add(dfs(land, i, j));
                    }
                }
            }
        int[] arr = res.stream().mapToInt(Integer::valueOf).toArray();
        Arrays.sort(arr);
        return arr;
    }

    /**
     * 从0开始深搜索
     * @param land 矩阵
     * @param row 行
     * @param col 列
     * @return 搜到的0的个数
     */
    int dfs(int[][] land, int row, int col){
         int num = 0;
        if(row < 0 || row >= land.length || col < 0 || col >= land[0].length || land[row][col] != 0){
            return num;
        }
        ++num;
        land[row][col] = -1; // 这一句简直神来之笔啊，不用复杂的数据结构保存遍历过的0
        num += dfs(land, row, col + 1) ;
        num += dfs(land, row, col - 1);
        num += dfs(land, row + 1, col);
        num += dfs(land, row - 1, col);
        num += dfs(land, row + 1, col + 1);
        num += dfs(land, row + 1, col - 1);
        num += dfs(land, row - 1, col + 1);
        num += dfs(land, row - 1, col - 1);
        return  num;
    }



         /*public int[] pondSizes(int[][] land) {
                List<Integer> list = new ArrayList<>();
                int temp;

                // 遍历矩阵每个元素
                for (int i = 0; i < land.length; i++) {
                    for (int j = 0; j < land[0].length; j++) {
                        temp = findPool(land, i, j);
                        if (temp != 0) list.add(temp);
                    }
                }

                // 第一种List<Integer>转int[]
                // int[] result = new int[list.size()];
                // for (int i = 0; i < result.length; i++) {
                //   result[i] = list.get(i);
                // }

                // 第二种List<Integer>转int[]，优雅且高效
                int[] result = list.stream().mapToInt(Integer::valueOf).toArray();

                Arrays.sort(result);

                return result;
            }

            private int findPool(int[][] land, int x, int y) {
                int num = 0;
                if (x < 0 || x >= land.length || y < 0 ||y>=land[0].length||land[x][y]!=0) {
                    return num;
                }
                num++;
                land[x][y] = -1;   // 如果为0，就转换为-1，避免重复搜索

                num += findPool(land, x + 1, y);
                num += findPool(land, x - 1, y);
                num += findPool(land, x, y + 1);
                num += findPool(land, x, y - 1);
                num += findPool(land, x + 1, y + 1);
                num += findPool(land, x + 1, y - 1);
                num += findPool(land, x - 1, y + 1);
                num += findPool(land, x - 1, y - 1);

                return num;
            }*/
}


